// The classes are basically the same as the BinaryTree 
// file except the visitor classes and the accept method
// in the Tree class

class TreeVisitor{
	public static void main(String[] a){
		System.out.println(new TV().Start());
	}
}

class TV {

	public int Start(){
		Tree root ;
		boolean ntb ;
		int nti ;
		MyVisitor v ;

		root = new Tree();
		ntb = root.Init(16);
		ntb = root.Print();
		System.out.println(100000000);
		ntb = root.Insert(8) ;
		ntb = root.Insert(24) ;
		ntb = root.Insert(4) ;
		ntb = root.Insert(12) ;
		ntb = root.Insert(20) ;
		ntb = root.Insert(28) ;
		ntb = root.Insert(14) ;
		ntb = root.Print();
		System.out.println(100000000);
		v = new MyVisitor();
		System.out.println(50000000);
		nti = root.accept(v);
		System.out.println(100000000);
		System.out.println(root.Search(24));
		System.out.println(root.Search(12));
		System.out.println(root.Search(16));
		System.out.println(root.Search(50));
		System.out.println(root.Search(12));
		ntb = root.Delete(12);
		ntb = root.Print();
		System.out.println(root.Search(12));

		return 0 ;
	}

}


class Tree{
	Tree left ;
	Tree right;
	int key ;
	boolean has_left ;
	boolean has_right ;
	Tree my_null ;



	//Tree new_node ;
	//Tree current_node ;
	//Tree parent_node ;

	// boolean ntb ;
	//boolean cont ;
	//boolean found ;
	//int ifound ;
	//  boolean is_root ;
	//  int     nti ;
	//  int key_aux ;
	// int auxkey1 ;
	// int auxkey2 ;

	public boolean Init(int v_key){
		key = v_key ;
		has_left = false ;
		has_right = false ;
		return true ;
	}

	public boolean SetRight(Tree rn){
		right = rn ;
		return true ;
	}

	public boolean SetLeft(Tree ln){
		left = ln ;
		return true ;
	}

	public Tree GetRight(){
		return right ;
	}

	public Tree GetLeft(){
		return left;
	}

	public int GetKey(){
		return key ;
	}

	public boolean SetKey(int v_key){
		key = v_key ;
		return true ;
	}

	public boolean GetHas_Right(){
		return has_right ;
	}

	public boolean GetHas_Left(){
		return has_left ;
	}

	public boolean SetHas_Left(boolean val){
		has_left = val ;
		return true ;
	}

	public boolean SetHas_Right(boolean val){
		has_right = val ;
		return true ;
	}

	public boolean Compare(int num1 , int num2){
		boolean ntb ;
		int nti ;

		ntb = false ;
		nti = num2 + 1 ;
		if (num1 < num2) ntb = false ;
		else if (!(num1 < nti)) ntb = false ;
		else ntb = true ;
		return ntb ;
	}

	public boolean Insert(int v_key){
		Tree new_node ;
		boolean ntb ;
		Tree current_node ;
		boolean cont ;
		int key_aux ;

		new_node = new Tree();
		ntb = new_node.Init(v_key) ;
		current_node = this ;
		cont = true ;
		while (cont){
			key_aux = current_node.GetKey();
			if (v_key < key_aux){
				if (current_node.GetHas_Left())
					current_node = current_node.GetLeft() ;
				else {
					cont = false ;
					ntb = current_node.SetHas_Left(true);
					ntb = current_node.SetLeft(new_node);
				}
			}
			else{
				if (current_node.GetHas_Right())
					current_node = current_node.GetRight() ;
				else {
					cont = false ;
					ntb = current_node.SetHas_Right(true);
					ntb = current_node.SetRight(new_node);
				}
			}
		}
		return true ;
	}

	public boolean Delete(int v_key){
		Tree current_node ;
		Tree parent_node ;
		boolean cont ;
		boolean found ;
		boolean ntb ;
		boolean is_root ;
		int key_aux ;

		current_node = this ;
		parent_node = this ;
		cont = true ;
		found = false ;
		is_root = true ;
		while (cont){
			key_aux = current_node.GetKey();
			if (v_key < key_aux)
				if (current_node.GetHas_Left()){
					parent_node = current_node ;
					current_node = current_node.GetLeft() ;
				}
				else cont = false ;
			else
			if (key_aux < v_key)
				if (current_node.GetHas_Right()){
					parent_node = current_node ;
					current_node = current_node.GetRight() ;
				}
				else cont = false ;
			else {
				if (is_root)
					if (!current_node.GetHas_Right() &&
							!current_node.GetHas_Left() )
						ntb = true ;
					else
						ntb = this.Remove(parent_node,current_node);
				else ntb = this.Remove(parent_node,current_node);
				found = true ;
				cont = false ;
			}
			is_root = false ;
		}
		return found ;
	}

	public boolean Remove(Tree p_node, Tree c_node){
		boolean ntb ;
		int auxkey1 ;
		int auxkey2 ;

		if (c_node.GetHas_Left())
			ntb = this.RemoveLeft(p_node,c_node) ;
		else
		if (c_node.GetHas_Right())
			ntb = this.RemoveRight(p_node,c_node) ;
		else {
			auxkey1 = c_node.GetKey();
			auxkey2 = (p_node.GetLeft()).GetKey() ;
			if (this.Compare(auxkey1,auxkey2)) {
				ntb = p_node.SetLeft(my_null);
				ntb = p_node.SetHas_Left(false);
			}
			else {
				ntb = p_node.SetRight(my_null);
				ntb = p_node.SetHas_Right(false);
			}
		}
		return true ;
	}

	public boolean RemoveRight(Tree p_node, Tree c_node){
		boolean ntb ;
		while (c_node.GetHas_Right()){
			ntb = c_node.SetKey((c_node.GetRight()).GetKey());
			p_node = c_node ;
			c_node = c_node.GetRight() ;
		}
		ntb = p_node.SetRight(my_null);
		ntb = p_node.SetHas_Right(false);
		return true ;
	}

	public boolean RemoveLeft(Tree p_node, Tree c_node){
		boolean ntb ;
		while (c_node.GetHas_Left()){
			ntb = c_node.SetKey((c_node.GetLeft()).GetKey());
			p_node = c_node ;
			c_node = c_node.GetLeft() ;
		}
		ntb = p_node.SetLeft(my_null);
		ntb = p_node.SetHas_Left(false);
		return true ;
	}


	public int Search(int v_key){
		Tree current_node ;
		int ifound ;
		boolean cont ;
		int key_aux ;

		current_node = this ;
		cont = true ;
		ifound = 0 ;
		while (cont){
			key_aux = current_node.GetKey();
			if (v_key < key_aux)
				if (current_node.GetHas_Left())
					current_node = current_node.GetLeft() ;
				else cont = false ;
			else
			if (key_aux < v_key)
				if (current_node.GetHas_Right())
					current_node = current_node.GetRight() ;
				else cont = false ;
			else {
				ifound = 1 ;
				cont = false ;
			}
		}
		return ifound ;
	}

	public boolean Print(){
		boolean ntb ;
		Tree current_node ;

		current_node = this ;
		ntb = this.RecPrint(current_node);
		return true ;
	}

	public boolean RecPrint(Tree node){
		boolean ntb ;

		if (node.GetHas_Left()){
			ntb = this.RecPrint(node.GetLeft());
		} else ntb = true ;
		System.out.println(node.GetKey());
		if (node.GetHas_Right()){
			ntb = this.RecPrint(node.GetRight());
		} else ntb = true ;
		return true ;
	}

	public int accept(Visitor v){
		int nti ;

		System.out.println(333);
		nti = v.visit(this) ;
		return 0 ;
	}

}



class Visitor {
	Tree l ;
	Tree r ;

	public int visit(Tree n){
		int nti ;

		if (n.GetHas_Right()){
			r = n.GetRight() ;
			nti = r.accept(this) ; }
		else nti = 0 ;

		if (n.GetHas_Left()) {
			l = n.GetLeft();
			nti = l.accept(this) ; }
		else nti = 0 ;

		return 0;
	}

}


class MyVisitor extends Visitor {

	public int visit(Tree n){
		int nti ;

		if (n.GetHas_Right()){
			r = n.GetRight() ;
			nti = r.accept(this) ; }
		else nti = 0 ;

		System.out.println(n.GetKey());

		if (n.GetHas_Left()) {
			l = n.GetLeft();
			nti =l.accept(this) ; }
		else nti = 0 ;

		return 0;
	}

}